k叉树 荷马史诗

题目 荷马史诗

思路分析

代码实现

#include <algorithm>

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

typedef long long LL;

typedef pair<LL, int> PLI;

const int N = 1e5 + 10;

int n, m;

priority_queue<PLI, vector<PLI>, greater<PLI>> heap;

int main() {

    cin >> n >> m;

    for (int i = 0; i < n; i++) {

        LL w;

        cin >> w;

        heap.push({w, 0});

    }

    while ((n - 1) % (m - 1)) {

        heap.push({0ll, 0});

        n++;

    }

    LL res = 0;

    while (heap.size() > 1) {

        LL sum = 0;

        int depth = 0;

        for (int i = 0; i < m; i++) {

            sum += heap.top().first;

            depth = max(depth, heap.top().second);

            heap.pop();

        }

        res += sum;

        heap.push({sum, depth + 1});

    }

    cout << res << endl;

    cout << heap.top().second << endl;

    return 0;

}

同类题型

视频讲解

⬅️ 雷达设备 🏠 00-刷题理模型 ➡️ 合并果子